/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import com.gwcloud.leetcode.common.datastructure.TreeNode;

/**
 * @ClassName   : Leetcode543 
 * @author      : ganwei 
 * @date        : 2020年5月3日
 * @Description : Leetcode543 二叉树的直径  
 */
public class Leetcode0543 {
	public int ans;
	/**
	 * -解题思路,递归思路,树的深度优先遍历
	 */
    public int diameterOfBinaryTree(TreeNode root) {
    	ans = 1;
    	depth(root);
    	return ans - 1;

    }
    
    public int depth(TreeNode node){
    	if(node == null){
    		return 0;
    	}
    	int L = depth(node.left);
    	int R = depth(node.right);
    	ans = Math.max(ans, L+R+1);
    	return Math.max(L, R) + 1;
    }

    
    public static void main(String[] args){
    	Leetcode0543 l543 = new Leetcode0543();
    	TreeNode t1 = new TreeNode(1);
    	TreeNode t2 = new TreeNode(2);
    	TreeNode t3 = new TreeNode(3);
    	TreeNode t4 = new TreeNode(4);
    	TreeNode t5 = new TreeNode(5);
    	
    	t1.left = t2;
    	//t1.right = t3;
    	t2.left = t4;
    	//t2.right = t5;
    	
    	System.out.println(l543.diameterOfBinaryTree(t1));
    	
    }
}
